/*
 * Heuristicas.h
 *
 *  Created on: Jun 2, 2009
 *      Author: gianpaolo
 */

#ifndef HEURISTICAS_H_
#define HEURISTICAS_H_
#define TRUE 1
#define FALSE 0
#define MAX_ITER 6 	//CONSTANTE para el GRASP
#define PORCENTAJE 0.6 //CONSTANTE para el maximo de iteraciones
#define TABU_MEM 100
#define MAXFLOAT 1000000
#include <math.h>
#include "Util.h"
#include "Lector.h"
#include "rngs.h"

/*
 * Algoritmo Greedy
 * El primer Vertice se pone en el conjunto S. Luego por cada vertice
 * se coloca en el lado que mejor quede
 * La tabla ya debe contener los valores seteados
 */
void greedy(int ** conexiones, int tamConex, int sInic[], int *sizeSol, int *valor);

/*
 * Algortimo random para la solucion inicial.
 * Por cada nodo se escoge de manera random si se coloca en una solucion o
 * en otra
 */
void randomnized(int **conexiones, int tamConex, int sInic[], int *sizeSol, int *valor);

/*
 * Genera una solucion inicial.
 * Por ahora la representacion de la solucion que genera es un arreglo que
 * tiene en la primera casilla el mejor primer candidato y en las demas basura
 * que se iran llenando mientras corra el algoritmo.
 *
 * Las Distintas maneras de generar la solucion inicial se encuentra en el util.c
 */
void generarSol(int ** conexiones, int tamConex, int sInic[], int *sizeSol, int* valor, short int opcion);

/*
 * Funcion random para la generacion de la solucion inicial.
 * En cada iteracion (de 0 hasta n) se escoge una lista de candidatos y de los
 * candidatos se escoge uno random para colocarlo asignarlo a alguno de los dos
 * conjuntos. Para ver mas informacion sobre como se escoge la lista de candidatos
 * buscar el paper "MIC2001_371_376.pdf" el cual se encuentra en esta distribucion
 * del proyecto
 */
void greedyRandom(int **conexiones, int tamConex, int sInic[], int *sizeSol, int *valor);

/*
 * Busqueda local aplicando el critero del primer mejor.
 * Recibe una solucion inicial de entrada y el tamano de
 * esa solucion
 */
void busquedaLocalPM(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Busqueda local aplicando el critero del mejor mejor.
 * Recibe una solucion inicial de entrada y el tamano de
 * esa solucion
 */
void busquedaLocalMM(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Busqueda local aplicando el critero de escoger un mejor random.
 * Recibe una solucion inicial de entrada y el tamano de
 * esa solucion
 */
void busquedaLocalMM(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Busqueda local teniendo una lista de candidatos (aquellos que mejoren la solucion)
 * y escogiendo uno random entre esos.
 */
void busquedaLocalSM(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Implementacion de la metaheuristica GRASP. Recibe como parametro una
 * solucion vacia en la cual se guardara la mejor solucion encontrada
 * despues de un numero MAX_ITER de iteraciones
 */
void grasp(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Iterated Local Search. Se corre alguno de los algoritmos de busqueda local.
 * Luego se perturba la solucion un poco y se vuelve a correr la busqueda local
 * por el mismo tiempo. Asi sucesivamente hasta que no hayan mejoras que hacerle a la
 * solucion.
 * La perturbacion puede o no mejorar la solucion. De igual manera se acepta.
 */
void lis(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);

/*
 * Implementacion de la metaheuristica Tabu para busqueda local.
 */
void tabu(int **conexiones, int tamConex, int sAct[], int *colaAct, int *valor);
#endif /* HEURISTICAS_H_ */
